1. Field of the Invention
The present invention relates generally to broadcast data encryption that uses encryption keys.
2. Description of the Related Art
The above-referenced applications disclose a system for encrypting publicly sold music, videos, and other content. As set forth therein, only authorized player-recorders can play and/or copy the content and only in accordance with rules established by the vendor of the content. In this way, pirated copies of content, which currently cost content providers billions of dollars each year, can be prevented.
In the encryption method disclosed in the above-referenced patent, authorized player-recorders are issued software-implemented device keys from a matrix of device keys. Specifically, the matrix of device keys includes plural rows and columns, and each authorized player-recorder is issued a single key from each column. Each column might contain many thousands of rows. The keys can be issued simultaneously with each other or over time, but in any event, no player-recorder is supposed to have more than one device key per column of the matrix. Although two devices might share the same key from the same column, the chances that any two devices share exactly the same set keys from all the columns of the matrix are very small when keys are randomly assigned.
Using any one of its device keys, an authorized player-recorder can decrypt a media key that in turn can be used to decrypt content that is contained on, e.g., a disk and that has been encrypted using the media key. Because the player-recorder is an authorized device that is programmed to follow content protection rules, it then plays/copies the content in accordance with predefined rules that protect copyright owners' rights in digitized, publicly sold content.
In the event that a device (and its keys) becomes compromised, deliberately or by mistake, it is necessary to revoke the keys of that device. The above-referenced documents describe how to do this. Revoking a set of keys effectively renders the compromised device (and any clones thereof) inoperable to play content that is produced after the revocation. Of course, since more than one device can share any particular key with the compromised device, revoking a set of device keys will result in revoking some keys held by innocent devices. When a small number of revocations occur this is not a problem, however, since only one key in a set is required for decryption, and it will be recalled that the chances that an innocent device shares an entire set of keys with any other device is very small. Accordingly, it is unlikely that revoking the set of keys of a compromised device will result in rendering an innocent device unable to decrypt content.
Nonetheless, as understood by the present invention it remains desirable that key overlap between devices remain small, because after potentially many compromised key set revocations, the chances of disabling/rendering useless an innocent device grow. Furthermore, it is desirable that the chance of any two devices having exactly the same set of keys is not only small, but approaches (or in fact is) zero, to altogether eliminate the possibility of debilitating an innocent device with a single revocation of a set of compromised keys. Moreover, as intimated above it is possible that the total number of key sets used in the system might approach one billion or more (since a billion or more devices might be manufactured). The present invention appreciates that when the number of device key sets approaches this magnitude, storing and accessing keys can require complex data storage structures. The present invention has made the critical observations noted above and has provided the below solutions to one or more of the observations.